import java.util.HashMap;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-11-12
 * Time: 22:39
 */
class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
public class Solution {
    //这种方法存在缺点，空间消耗太大，既递归又产生了很多新的数组
    //找到中序数组中根节点的位置
    /*public int rootIndex(int[] inorder,int root){
        for(int i=0;i<inorder.length;i++){
            if(inorder[i]==root){
                return i;
            }
        }
        return -1;
    }
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length==0){
            return null;
        }
        int index=rootIndex(inorder,preorder[0]);
        TreeNode root=new TreeNode(preorder[0]);
        //分治，根据左右子树长度利用Arrays.copyOfRange方法划分数组
        //递归构建左子树
        //根据根节点下标把先序中序数组分为两部分，递归分治构建二叉树
        //左子树有几个要根据长度来计算，左子树的长度就是根节点在中序数组的下标减去0下标
        // 然后在先序数组中左子树就是从1开始到左子树的长度+1的位置，因为在copyOfRange中不会到达长度+1的位置
        //左子树在中序数组的位置就是从0到根节点下标的位置
        root.left= buildTree(Arrays.copyOfRange(preorder,1,index+1),
                             Arrays.copyOfRange(inorder,0,index));
        //递归构建右子树
        //右子树在先序数组的位置就是从根节点位置+左子树的长度+1开始到先序数组的长度-1的位置
        //右子树在中序数组的位置就是从根节点的位置+1开始到中序数组的长度-1的位置
        root.right=buildTree(Arrays.copyOfRange(preorder,index+1, preorder.length),
                             Arrays.copyOfRange(inorder,index+1,inorder.length));
        return root;
    }*/
    
    //法二:利用根节点的下标计算出左右子树的长度之后，通过左右子树的长度来循环数组，减少了空间消耗
    HashMap<Integer,Integer> map=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder==null || inorder==null){
            return null;
        }
        for(int i=0;i<inorder.length;i++){
            map.put(inorder[i],i);
        }
        return partition(preorder,0,preorder.length-1,inorder,0,inorder.length-1);
    }
    
    //每一次递归做的事其实就是把先序数组的每一个节点当做根节点，然后找到它在中序数组的位置，把左右子树的每一个节点当做根节点来做
    private TreeNode partition(int[] preorder, int preStart, int preEnd, int[] inorder, int inStart, int inEnd) {
        if(preStart>preEnd){
            return null;
        }
        //确定根节点
        int rootVal=preorder[preStart];
        //确定根节点在中序数组的位置
        int index=map.get(rootVal);
        //确定左子树的长度
        int leftSize=index- inStart;
        //构建二叉树
        //先确定根节点
        TreeNode root=new TreeNode(rootVal);
        //递归分治构建左右子树
        root.left=partition(preorder,preStart+1,preStart+leftSize,inorder,inStart,index-1);
        root.right=partition(preorder,preStart+leftSize+1,preEnd,inorder,index+1,inEnd);
        return root;
    }
}
